
# coding:utf-8


class SingleNode(object):
    """单链表的节点类"""
    def __init__(self, value):
        self.value = value
        self.next = None


class SingleLinkList(object):
    """单链表类"""
    def __init__(self, node=None):
        self.head = node

    def is_empty(self):
        """判断链表是否为空"""
        if self.head is None:
            print("链表为空")
            return True
        else:
            return False

    def length(self):
        """输出链表长度"""
        if self.is_empty():
            print("链表为空,长度为0")
            return 0
        else:
            list_len = 1
            temp_node = self.head
            while temp_node.next is not None:
                list_len += 1
                temp_node = temp_node.next
            print("链表长度为%d" % list_len)
            return list_len

    def travel(self):
        """遍历打印链表"""
        if self.is_empty():
            print("链表为空")
        else:
            temp_node = self.head
            while temp_node.next is not None:
                print(temp_node.value, end=",")
                temp_node = temp_node.next
            print(temp_node.value)

    def add(self, node):
        """向链表头部添加元素"""
        node.next = self.head
        self.head = node

    def append(self, node):
        """向链表尾部添加元素"""
        if self.is_empty():
            self.head = node
        else:
            temp_node = self.head
            while temp_node.next is not None:
                temp_node = temp_node.next
            temp_node.next = node

    def insert(self, pos, node):
        """向指定位置添加元素"""
        if pos <= 0:
            print("插入位置从1开始")
        elif self.length() < pos - 1:
            print("链表长度小于要插入的位置")
        elif self.length() == pos - 1:
            self.append(node)
        elif pos == 1:
            self.add(node)
        else:
            temp_node = self.head
            # 找到要插入的节点的位置的上一个节点
            while temp_node.next is not None and pos != 2:
                temp_node = temp_node.next
                pos -= 1
            node.next = temp_node.next
            temp_node.next = node

    def remove(self, node):
        """删除节点"""
        if self.is_empty():
            print("链表为空")
        else:
            index = self.search(node)
            if index:
                if index == 1:
                    self.head = self.head.next
                else:
                    temp_node = self.head
                    # 找到要删除的节点的前一个节点
                    while temp_node.next is not None and index != 2:
                        temp_node = temp_node.next
                        index -= 1
                    temp_node.next = temp_node.next.next
                    print("节点已删除")
            else:
                print("节点中无此元素")

    def search(self, node):
        """查找节点是否存在"""
        if self.is_empty():
            print("链表为空，要查找的元素不存在")
        else:
            temp_node = self.head
            index = 1
            if temp_node.value == node.value:
                return index
            while temp_node.next is not None and temp_node.value != node.value:
                index += 1
                temp_node = temp_node.next
            if temp_node.value == node.value:
                print("找到节点，位置为%d" % index)
                return index
            else:
                print("节点不存在")
                return 0


if __name__ == "__main__":
    n1 = SingleNode(1)
    n2 = SingleNode(2)
    n3 = SingleNode(3)
    n4 = SingleNode(4)
    n5 = SingleNode(5)
    n6 = SingleNode(6)

    single_list = SingleLinkList()
    single_list.travel()
    print("----------")
    single_list.add(n1)
    single_list.add(n2)
    single_list.travel()
    print("----------")
    single_list.append(n3)
    single_list.append(n4)
    single_list.travel()
    single_list.length()
    print("----------")

    single_list.insert(1, n5)
    single_list.travel()
    print("----------")

    single_list.search(n4)
    single_list.travel()
    print("----------")

    single_list.remove(n1)
    single_list.remove(n2)
    single_list.remove(n3)
    single_list.remove(n4)
    single_list.remove(n5)
    single_list.travel()
    print("----------")












